
"""
889. 根据前序和后序遍历构造二叉树
"""
from typing import List, Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.dict = {}

    """
     * 分解二叉树
     * 二叉树定义：构建出二叉树，先构建根节点，再构建左节点，右节点
     * 特点：前序遍历的顺序为：根节点，左子树，右子树
     *     后序遍历的顺序为：左子树，右子树，根节点
     *     第一步，建根节点：前序的第一个值
     *     第二步，定左子树范围，中序的第二个节点是左子节点，从后续遍历最后一个节点到左子节点的距离就是右子树的个数，进而确定了左右子树的范围
    """
    def constructFromPrePost(self, preorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 将后序遍历的值存入字典，用于定位索引
        for i in range(len(postorder)):
            self.dict[postorder[i]] = i
        return self.build(preorder, 0, len(preorder) - 1, postorder, 0, len(postorder) - 1)

    '''遍历二叉树'''
    def build(self, preorder: List[int], pre_start: int, pre_end: int, postorder: List[int], post_start: int, post_end: int) -> Optional[TreeNode]:
        if pre_start > pre_end:
            return None
        if pre_start == pre_end:
            return TreeNode(preorder[pre_start])

        root = TreeNode(preorder[pre_start])
        # 获取左节点在后序遍历的位置
        post_left_index = self.dict[preorder[pre_start + 1]]
        left_size = post_left_index - post_start + 1
        # 前序位置
        root.left = self.build(preorder, pre_start + 1, pre_start + left_size, postorder, post_start, post_left_index)
        # 中序位置
        root.right = self.build(preorder, pre_start + left_size + 1, pre_end, postorder, post_left_index + 1, post_end - 1)
        # 后序位置
        return root
